/*
 *
 *
Copyright (c) 1998-2001 Aristar, Inc. All rights reserved.

Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.

3. The end-user documentation included with the redistribution, if any,
must include the following acknowledgment:

"This product includes software developed by Aristar, Inc. (http://www.aristar.com/)."

Alternately, this acknowledgment may appear in the software itself, if and
wherever such third-party acknowledgments normally appear.

4. The names "Dialect" and "Aristar, Inc." must not be used to endorse or
promote products derived from this software without prior written permission.
For written permission, please contact info@aristar.com.

5. Products derived from this software may not be called "Dialect", nor may
"Dialect" appear in their name, without prior written permission of Aristar, Inc.

THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
ARISTAR, INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

This software consists of voluntary contributions made by many individuals
on behalf of Aristar, Inc.  For more information on Aristar, Inc.,
please see <http://www.aristar.com/>.

Portions of this software are based upon software freely available and
written by individuals not associated with Aristar, Inc.  Copyrights are
maintained in the relevant source code files.
 *
 *
 */

#include "stdafx.h"
#include "_bigint.h"

#ifdef CRYPTO_SUPPORT

//
//
//	This whole class could use some serious optimizing some day.
//	There is also almost no buffer overflow checking, etc.
//
//

bigint::bigint()
{
	m_Length = 0;
	memset(m_Bytes, 0, sizeof(m_Bytes));
}

bigint::bigint(const bigint& init)
{
	m_Length = init.m_Length;
	memcpy(m_Bytes, init.m_Bytes, sizeof(m_Bytes));
}

bigint::bigint(CString init)
{
	m_Length = 0;
	memset(m_Bytes, 0, sizeof(m_Bytes));

	if (init.GetLength() != 0) {
		DecodeHex(init, m_Bytes, m_Length);
	}
}

bigint::bigint(unsigned char buf[], int length, bool bBigEndian)
{
	memset(m_Bytes, 0, sizeof(m_Bytes));

	m_Length = length;
	if (bBigEndian) {
		for (int idx = 0; idx < length; ++idx) {
			m_Bytes[idx] = buf[length - idx - 1];
		}
	}
	else {
		memcpy(m_Bytes, buf, length);
	}
}

bigint::bigint(int init)
{
	ASSERT(false); // Add later...
}

bigint::~bigint(){}

////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////

bool bigint::DecodeHex(CString textIn, unsigned char* out, int& outLength) const
{
	// x = [:{encoding:"hex"}, "a8f1234":]

	int ascii_count = textIn.GetLength();
	LPCTSTR ascii_data, ascii_data_head;
	ascii_data_head = textIn;
	ascii_data = ascii_data_head + ascii_count - 1; // Walk backwards

	int bin_count = ascii_count / 2 + 1;		// Possible over estimate
	unsigned char *bin_data, *bin_data_head;
	bin_data_head = new unsigned char[bin_count];
	bin_data = bin_data_head + bin_count;		// Walk backwards

	TCHAR ch;
	unsigned char bits = 0, val;
	bin_count = 0;
	while (ascii_data >= ascii_data_head) {
		val = 0;
		ch = *ascii_data--;
		if (ch <= ' ') continue;
		else if ((ch >= '0') && (ch <= '9')) {
			val = ch - '0';
		}
		else if ((ch >= 'a') && (ch <= 'f')) {
			val = ch - 'a' + 10;
		}
		else if ((ch >= 'A') && (ch <= 'F')) {
			val = ch - 'A' + 10;
		}
		else {
			delete[] bin_data_head;
			return false;
		}

		if (bits == 0) {
			--bin_data;
			++bin_count;
			*bin_data = val;
			bits = 4;
		}
		else {
			*bin_data = *bin_data | (val << 4);
			bits = 0;
		}
	}

	// Place data in output buffer (LSB first)
	outLength = bin_count;
	for (int idx = 0; idx < bin_count; ++idx) {
		out[idx] = bin_data[bin_count - idx - 1];
	}

	// Remove zeros from MSB positions
	for (idx = bin_count - 1; idx >= 0; --idx) {
		if (out[idx] == 0) --outLength;
		else break;
	}

	delete[] bin_data_head;
	return true;
}

static TCHAR tohex_table[16] = {
	'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'
};

bool bigint::EncodeHex(const unsigned char *bin_data, int bin_len, CString& textOut) const
{
	textOut.Empty();
	int column = 0;
	for (int idx = bin_len - 1; idx >= 0; --idx) {
		textOut += tohex_table[(bin_data[idx] & 0xF0) >> 4];
		textOut += tohex_table[bin_data[idx] & 0xF];
	}
	return true;
}

////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////

const unsigned char* bigint::GetBytes() const
{
	return m_Bytes;
}

CString bigint::ToString() const
{
	CString result;
	if (m_Length == 0) {
		result = _T("0");
	}
	else {
		EncodeHex(m_Bytes, m_Length, result);
	}
	return result;
}

inline void bigint::AddDigit(int value)
{
	ASSERT(m_Length < MAX_BYTES - 1);
	m_Bytes[m_Length++] = value;
}

inline int bigint::GetDigit(int index) const
{
	return (index < m_Length) ? m_Bytes[index] : 0;
}

inline void bigint::SetDigit(int index, int value)
{
	if (index < m_Length) {
		m_Bytes[index] = value;
	}
	else {
		ASSERT(false);
	}
}

bigint& bigint::operator = (const bigint& rhs)
{
	m_Length = rhs.m_Length;
	memcpy(m_Bytes, rhs.m_Bytes, sizeof(m_Bytes));
	return *this;
}

bigint& bigint::operator ^= (const bigint& rhs)
{
	if (rhs.m_Length > m_Length) {
		// Assumption that the "new" bytes are still zero initialized
		m_Length = rhs.m_Length;
	}

	for (int idx = 0; idx < m_Length; ++idx) {
		m_Bytes[idx] ^= rhs.m_Bytes[idx];
	}
	return *this;
}

bool bigint::operator == (const bigint& rhs) const
{
	if (this == &rhs) return true;
	else if (m_Length != rhs.m_Length) {
		if ((m_Length == 0) && (rhs.m_Length == 1)) {
			return rhs.GetDigit(0) == 0;
		}
		else if ((m_Length == 1) && (rhs.m_Length == 0)) {
			return GetDigit(0) == 0;
		}
		return false;
	}
	else {
		return memcmp(m_Bytes, rhs.m_Bytes, m_Length) == 0;
	}
}

bool bigint::operator != (const bigint& rhs) const
{
	if (this == &rhs) return false;
	else if (m_Length != rhs.m_Length) {
		if ((m_Length == 0) && (rhs.m_Length == 1)) {
			return rhs.GetDigit(0) != 0;
		}
		else if ((m_Length == 1) && (rhs.m_Length == 0)) {
			return GetDigit(0) != 0;
		}
		return true;
	}
	else {
		return memcmp(m_Bytes, rhs.m_Bytes, m_Length) != 0;
	}
}

bool bigint::operator > (const bigint& rhs) const
{
	if (this == &rhs) return false;
	else if (m_Length > rhs.m_Length) return true;
	else if (m_Length < rhs.m_Length) return false;
	else {
		// Compare MSB -> LSB
		for (int idx = m_Length - 1; idx >= 0; --idx) {
			if (m_Bytes[idx] > rhs.m_Bytes[idx]) return true;
			else if (m_Bytes[idx] < rhs.m_Bytes[idx]) return false;
		}
		ASSERT(*this == rhs);
		return false; // They must be equal if we hit this point
	}
}

bool bigint::operator >= (const bigint& rhs) const
{
	if (this == &rhs) return true;
	else if (m_Length > rhs.m_Length) return true;
	else if (m_Length < rhs.m_Length) return false;
	else {
		// Compare MSB -> LSB
		for (int idx = m_Length - 1; idx >= 0; --idx) {
			if (m_Bytes[idx] > rhs.m_Bytes[idx]) return true;
			else if (m_Bytes[idx] < rhs.m_Bytes[idx]) return false;
		}
		ASSERT(*this == rhs);
		return true; // They must be equal if we hit this point
	}
}

bool bigint::operator < (const bigint& rhs) const
{
	if (this == &rhs) return false;
	else if (m_Length < rhs.m_Length) return true;
	else if (m_Length > rhs.m_Length) return false;
	else {
		// Compare MSB -> LSB
		for (int idx = m_Length - 1; idx >= 0; --idx) {
			if (m_Bytes[idx] < rhs.m_Bytes[idx]) return true;
			else if (m_Bytes[idx] > rhs.m_Bytes[idx]) return false;
		}
		ASSERT(*this == rhs);
		return false; // They must be equal if we hit this point
	}
}

bool bigint::operator <= (const bigint& rhs) const
{
	if (this == &rhs) return true;
	else if (m_Length < rhs.m_Length) return true;
	else if (m_Length > rhs.m_Length) return false;
	else {
		// Compare MSB -> LSB
		for (int idx = m_Length - 1; idx >= 0; --idx) {
			if (m_Bytes[idx] < rhs.m_Bytes[idx]) return true;
			else if (m_Bytes[idx] > rhs.m_Bytes[idx]) return false;
		}
		ASSERT(*this == rhs);
		return true; // They must be equal if we hit this point
	}
}

void bigint::Increment()
{
	// Destructively add 1 to this
	int sum = 0;
	int carry = 1;
	for (int idx = 0; idx < m_Length; ++idx) {
		sum = GetDigit(idx) + carry;
		if (sum < 256) {
			SetDigit(idx, sum);
			return;
		}
		else {
			carry = sum >> 8;	//carry = sum / 256;
			sum &= 0xFF;		//sum %= 256;
			SetDigit(idx, sum);
		}
	}

	if (carry != 0) {
		AddDigit(carry);
	}
}

bigint& bigint::operator += (const bigint& rhs)
{
	int sum = 0;
	int carry = 0;
	int length = m_Length > rhs.m_Length ? m_Length : rhs.m_Length;

	for (int idx = 0; idx < length; ++idx) {
		sum = GetDigit(idx) + rhs.GetDigit(idx) + carry;
		carry = sum >> 8;	//carry = sum / 256;
		sum &= 0xFF;		//sum %= 256;
		if (idx < m_Length) {
			m_Bytes[idx] = sum;
		}
		else {
			AddDigit(sum);
		}
	}

	if (carry != 0) {
		AddDigit(carry);
	}
	return *this;
}

bigint bigint::operator + (const bigint& rhs)
{
	bigint result;

	int sum = 0;
	int carry = 0;
	int length = m_Length > rhs.m_Length ? m_Length : rhs.m_Length;

	for (int idx = 0; idx < length; ++idx) {
		sum = GetDigit(idx) + rhs.GetDigit(idx) + carry;
		carry = sum >> 8;	//carry = sum / 256;
		sum &= 0xFF;		//sum %= 256;
		result.AddDigit(sum);
	}

	if (carry != 0) {
		result.AddDigit(carry);
	}

	return result;
}

bigint bigint::operator - (const bigint& rhs)
{
	ASSERT(*this >= rhs);

	bigint result;

	int diff = 0;
	int borrow = 0;

	for (int idx = 0; idx < m_Length; ++idx) {
		diff = GetDigit(idx) - rhs.GetDigit(idx) - borrow;
		if (diff >= 0) {
			borrow = 0;
		}
		else {
			diff += 256;
			borrow = 1;
		}
		result.AddDigit(diff);
	}

	// Remove zero bytes from MSB
	for (idx = result.m_Length - 1; idx >= 0; --idx) {
		if (result.m_Bytes[idx] == 0) result.m_Length--;
		else break;
	}

	return result;
}

bigint bigint::operator * (const bigint& rhs)
{
	bigint lhs(*this);
	bigint product, temp;
	int digit, sum, carry = 0;

	int lenrhs = rhs.m_Length;
	int lenlhs = lhs.m_Length;

	for (int xx = 0; xx < lenrhs; ++xx) {
		carry = 0;
		digit = rhs.GetDigit(xx);
		temp = bigint();
		for (int aa = 0; aa < xx; ++aa) {
			temp.AddDigit(0);
		}
		for (int yy = 0; yy < lenlhs; ++yy) {
			sum = lhs.GetDigit(yy) * digit + carry;
			carry = sum >> 8;	//carry = sum / 256;
			sum &= 0xFF;		//sum %= 256;
			temp.AddDigit(sum);
		}
		if (carry != 0) {
			ASSERT(carry < 256);
			temp.AddDigit(carry);
		}
		product += temp;	//product = product + temp;
	}

	return product;
}

bigint bigint::operator / (const bigint& rhs)
{
	bigint quotient, remainder;
	divide(*this, rhs, quotient, remainder);
	return quotient;
}

bigint bigint::operator % (const bigint& rhs)
{
	bigint quotient, remainder;
	divide(*this, rhs, quotient, remainder);
	return remainder;
}

void bigint::divide(bigint dividend, bigint divisor, bigint& quotient, bigint& remainder)
{
	// This is for unsigned division only!!!

	quotient = bigint();
	remainder = bigint();

	if (divisor == bigint()) {
		ASSERT(false);
		return; // div-by-zero
	}
	else if (divisor == dividend) {
		quotient.AddDigit(1);
		return;
	}
	else if (divisor > dividend) {
		remainder = dividend;
		return;
	}

	unsigned int bytes = dividend.m_Length > divisor.m_Length ? dividend.m_Length : divisor.m_Length;
	int bits = bytes << 3;
	unsigned int bit;
	bigint d, t;

	while (remainder < divisor) {
		bit = (dividend.GetDigit(bytes - 1) & 0x80) >> 7; // Grab most sig bit

		remainder.LeftShiftIP();
		if (bit) {
			if (remainder.m_Length == 0) remainder.AddDigit(bit);
			else remainder.SetDigit(0, remainder.GetDigit(0) | bit);
		}

		d = dividend;
		dividend.LeftShiftIP();
		--bits;
	}

	// Undo last loop from above
	dividend = d;
	remainder = remainder.RightShift();
	++bits;

	for (int idx = 0; idx < bits; ++idx) {
		remainder.LeftShiftIP();
		if ((dividend.GetDigit(bytes - 1) & 0x80) >> 7) {
			if (remainder.m_Length == 0) remainder.AddDigit(1);
			else remainder.SetDigit(0, remainder.GetDigit(0) | 1);
		}
		dividend.LeftShiftIP();
		quotient.LeftShiftIP();
		if (remainder >= divisor) {
			if (quotient.m_Length == 0) quotient.AddDigit(1);
			else quotient.SetDigit(0, quotient.GetDigit(0) | 1);
			remainder = remainder - divisor;
		}
	}
}

void bigint::LeftShiftIP()
{
	// Do:  this = this << 1
	unsigned int digit, carry = 0;
	for (int idx = 0; idx < m_Length; ++idx) {
		digit = m_Bytes[idx];
		if (idx < m_Length) {
			SetDigit(idx, ((digit << 1) | carry) & 0xFF);
		}
		else {
			AddDigit(((digit << 1) | carry) & 0xFF);
		}
		carry = (digit & 0x80) >> 7;
	}
	if (carry) {
		AddDigit(1);
	}
}

bigint bigint::LeftShift() const
{
	// Do:  result = this << 1
	bigint result;
	unsigned int digit, carry = 0;
	for (int idx = 0; idx < m_Length; ++idx) {
		digit = m_Bytes[idx];
		result.AddDigit(((digit << 1) | carry) & 0xFF);
		carry = (digit & 0x80) >> 7;
	}
	if (carry) {
		result.AddDigit(1);
	}
	return result;
}

bigint bigint::RightShift() const
{
	// Do:  this >> 1
	bigint result;
	unsigned int digit, carry = 0;

	int startIdx = m_Length - 1;
	if (m_Bytes[startIdx] == 1) {
		carry = 0x80;
		--startIdx;
	}
	result.m_Length = startIdx + 1;

	for (int idx = startIdx; idx >= 0; --idx) {
		digit = m_Bytes[idx];
		result.m_Bytes[idx] = ((digit >> 1) | carry) & 0xFF;
		carry = (digit & 1) << 7;
	}
	return result;
}

inline int bigint::GetBit(int index) const
{
	//return (m_Bytes[index >> 3] & (1 << (index & 7))) ? 1 : 0;
	return (m_Bytes[index >> 3] >> (index & 7)) & 0x1;
}

void bigint::SetBit(int index, int value)
{
	m_Bytes[index >> 3] |= (1 << (index & 7));
}

bigint bigint::ModularExp(const bigint& a, const bigint& b, const bigint& n)
{
	//
	// return (a ^ b) mod n
	// Using algorithm from Introduction to Algorithms page 829
	//
	bigint c;
	bigint d;
	d.AddDigit(1);

	int bytes = b.m_Length;
	int bits = bytes << 3;

	// Trim any leading zeros in the MSB
	while (b.GetBit(bits - 1) == 0)
		--bits;

	for (int idx = bits - 1; idx >= 0; --idx) {
		c.LeftShiftIP(); // Mult by 2
		d = (d * d) % n;
		if (b.GetBit(idx) == 1) {
			c.Increment();	// c = c + 1
			d = (d * a) % n;
		}
	}
	return d;
}

void bigint::Rand(int bytes)
{
	// This is not really a crypto level RNG, but it should do for now
	static bool b = true;
	if (b) {
		b = false;
		srand(GetTickCount());
	}
	unsigned int t = GetTickCount();
	m_Length = bytes;
	for (int idx = 0; idx < bytes; ++idx) {
		m_Bytes[idx] = (rand() ^ idx ^ t) & 0xFF;
	}
}

#endif // #ifdef CRYPTO_SUPPORT
